/*
 * Copyright (c) 2010.
 * All Rights Reserved.
 *
 * Author : Madhur Raj
 */

#include "sudoku.h"

void printSudoku()
{
   int i, j;

   printf (" ##################################\n");
   for (i=0; i<9; i++)
   {
      for (j=0; j<9; j++)
      {
         printf(" %d", mBox[i/3][j/3].succSeq[i%3][j%3]);
#if DEBUG
         printf ("p%d", mBox[i/3][j/3].probCount[i%3][j%3]);
         printf ("s%d", mBox[i/3][j/3].succCount);
#endif
      }
      printf("\n");
   }
   printf (" ##################################\n");
   return;
}

void printString()
{
   int i,j;
   char temp;

   for (i=0; i<158; i++)
   {
      temp = 0;
      for (j=0; j<4; j++)
      {
         temp = (message[i] & (0xff << (8*j))) >> (j*8);
      }
   }
   return;
}

int testRows()
{
   int i,j;
   static int relinquisher[11];

   for (i=0; i<9; i++)
   {
      for (j=0; j<=9; j++)
      {
         relinquisher[j] = 0;
      }
      for (j=0; j<9; j++)
      {
         if (!mBox[i/3][j/3].succSeq[i%3][j%3])
            continue;
         if(!relinquisher[mBox[i/3][j/3].succSeq[i%3][j%3]])
         {
            relinquisher[mBox[i/3][j/3].succSeq[i%3][j%3]] = 1;
         }
         else
         {
#ifdef DEBUG
            printf("%d %d\n", i, j);
#endif
            return (FAILED);
         }
      }
   }
   return (SUCCESS);
}

int testColumns()
{
   int i,j;
   static int relinquisher[11];

   for (i=0; i<9; i++)
   {
      for (j=0; j<=9; j++)
      {
         relinquisher[j] = 0;
      }
      for (j=0; j<9; j++)
      {
         if (!mBox[j/3][i/3].succSeq[j%3][i%3])
            continue;
         if(!relinquisher[mBox[j/3][i/3].succSeq[j%3][i%3]])
         {
            relinquisher[mBox[j/3][i/3].succSeq[j%3][i%3]] = 1;
         }
         else
         {
#ifdef DEBUG
            printf("%d %d\n", i, j);
#endif
            return (FAILED);
         }
      }
   }
   return (SUCCESS);
}

int testForUniqueness()
{
   int ret; 
   
   ret = testRows();
   if(!ret)
      ret = testColumns();

   return (ret);
}

int validateForSuccess()
{
   int i, j;
   int ret;

   ret = 0;
   ret = testForUniqueness();
   if (ret)
      return(ret);

   for (i=0; i<9; i++)
   {
      for (j=0; j<9; j++)
      {
         if(!mBox[i/3][j/3].succSeq[i%3][j%3])
         {
#ifdef DEBUG1
            printSudoku();
#endif
            return (DATINSUFF);
         }
      }
   }

   return (ret);
}


void updateBox()
{
   int i, j, k;
   int row, col;

   for (i=0; i<3; i++)
   {
      for (j=0; j<3; j++)
      {
         mBox[i][j].succCount = 0;
         for (row=0; row<3; row++)
         {
            for (col=0; col<3; col++)
            {
               mBox[i][j].probCount[row][col] = 0;
            }
         }
      }
   }

   for(i=0; i<9; i++)
   {
      for(j=0; j<9; j++)
      {
         if (presetVal[i][j])
         {
            mBox[i/3][j/3].succSeq[i%3][j%3] = presetVal[i][j];
            mBox[i/3][j/3].succCount++;
            for (k=0; k<9; k++)
            {
               mBox[i/3][j/3].probSeq[i%3][j%3][k] = 0;
            }
         }
         else 
         {
            for (k=0; k<9; k++)
            {
               mBox[i/3][j/3].probSeq[i%3][j%3][k] = k + 1;
               mBox[i/3][j/3].succSeq[i%3][j%3]    = 0;
               mBox[i/3][j/3].probCount[i%3][j%3]++;
            }

         }
      }
   }

#ifdef DEBUG1
   printSudoku();
#endif
   return ;
}

void readfile()
{
   FILE *fp;
   char *cStr;
   int i,j;
   int len;

   fp = fopen("readfile.txt", "r");
   if (!fp)
   {
      printf("Failed to read file\n");
      return;
   }

   fseek(fp, 0L, SEEK_END); /* Move to the end of file */
   len = ftell(fp);         /* Get the length */
   rewind(fp);           /* Get back to start of file */

   cStr = calloc(len + 1, sizeof(char));

   if (cStr == NULL)
   {
      printf(" Insufficient memory\n");
      return ;
   }

   fread(cStr, len, 1, fp);
   i = j = 0;

   while (*cStr)
   {
      if (*cStr - '0' <= 9 && *cStr - '0' >= 0)
      {
         presetVal[i][j++] = *cStr - '0';
      }
      if (j == 9)
      {
         i++; j = 0;
      }
      cStr++;
   }

   for (i=0; i<9; i++)
   {
      for(j=0; j<9; j++)
      {
         printf(" %d ", presetVal[i][j]);
      }
      printf("\n");
   }

   updateBox();

   return ;
}

void processCurrBox(int nr, int nc, int row, int col)
{
   int i,j;
   int temp;

   for (i=0; i<3; i++)
   {
      for (j=0; j<3; j++)
      {
         temp = mBox[nr][nc].succSeq[i][j];
         if(temp && mBox[nr][nc].probSeq[row][col][temp - 1])
         {
#ifdef DEBUG
            printf(" ps%d", mBox[nr][nc].probSeq[row][col][temp - 1]);
#endif
            mBox[nr][nc].probSeq[row][col][temp - 1] = 0;
            mBox[nr][nc].probCount[row][col]--;
         }
      }
   }
   return;
}

void processRow(int nr, int nc, int row, int col)
{
   int i,j;
   int temp;

   for (i=0; i<3; i++)
   {
      for(j=0; j<3; j++)
      {
         temp = mBox[nr][i].succSeq[row][j];
         if(temp && mBox[nr][nc].probSeq[row][col][temp - 1])
         {
#ifdef DEBUG
            printf(" ps%d", mBox[nr][nc].probSeq[row][col][temp - 1]);
#endif
            mBox[nr][nc].probSeq[row][col][temp - 1] = 0;
            mBox[nr][nc].probCount[row][col]--;
         }
      }
   }
   return;
}

void processCol(int nr, int nc, int row, int col)
{
   int i,j;
   int temp;

   for (i=0; i<3; i++)
   {
      for(j=0; j<3; j++)
      {
         temp = mBox[i][nc].succSeq[j][col];
         if(temp && mBox[nr][nc].probSeq[row][col][temp - 1])
         {
#ifdef DEBUG
            printf(" ps%d", mBox[nr][nc].probSeq[row][col][temp - 1]);
#endif
            mBox[nr][nc].probSeq[row][col][temp - 1] = 0;
            mBox[nr][nc].probCount[row][col]--;
         }
      }
   }
   return;
}

void testForSuccess(int nr, int nc, int row, int col)
{
   int i;
   int temp;

   if (mBox[nr][nc].probCount[row][col] == 1)
   {
      for (i=0; i<9; i++)
      {
         temp = mBox[nr][nc].probSeq[row][col][i];
         if (temp)
         {
            mBox[nr][nc].succSeq[row][col] = temp;
            mBox[nr][nc].succCount++;
            globSucc++;
         }
      }
   }
   return;
}


void processBox(int nr, int nc)
{
   int row, col;
   for (row=0; row<3; row++)
   {
      for(col=0; col<3; col++)
      {
         if (!mBox[nr][nc].succSeq[row][col])
         {
            processCurrBox(nr, nc, row, col);
            testForSuccess(nr, nc, row, col);
            processRow(nr, nc, row, col);
            testForSuccess(nr, nc, row, col);
            processCol(nr, nc, row, col);
            testForSuccess(nr, nc, row, col);
         }
      }
   }
   return;
}


void solveSudoku()
{
   int   row, col, wid;
   int   temp;

   while (1)
   {
      temp = globSucc;
      for (row=0; row<3; row++)
      {
         for (col=0; col<3; col++)
         {
            processBox(row, col);
         }
      }
      if (temp == globSucc)
        break; 
   }
   return;
}

void insertNode(int r, int c)
{
   Node *node; 
   Node *tempNode; 
   int  i;
   int  j = 0;

   node = (Node*)malloc(sizeof(Node));

   node->nr          = r/3;
   node->nc          = c/3;
   node->row         = r%3;
   node->col         = c%3;
   node->probCount   = mBox[r/3][c/3].probCount[r%3][c%3];
   node->next        = NULL;
   node->prev        = NULL;

   for (i=0; i<9; i++)
   {
      if (mBox[r/3][c/3].probSeq[r%3][c%3][i])
      {
         node->probSeq[j++] = mBox[r/3][c/3].probSeq[r%3][c%3][i];
      }
   }
   if (gNode)
   {
      tempNode = gNode;
      while (tempNode->next != NULL)
      {
         tempNode = tempNode->next;
      }
      tempNode->next = node;
      node->prev  = tempNode;
   }
   else
   {
      gNode = node;
   }

   gNumNode++;

   return;
}

#ifdef DEBUG
void printNodes()
{
   Node *currNode;

   currNode = gNode;

   while (currNode)
   {
      printf(" %d ", currNode->probCount);
      currNode = currNode->next;
   }
   printf("\n");
   return;
}
#endif

void sortNodes()
{
   char truth;
   Node *node;
   Node *sortNode;
   Node *lstNode;
   Node *grstNode;
   Node *currNode;
   Node *tempCurrNode;
   node = gNode;
   currNode = gNode;
   lstNode  = currNode;
   grstNode = lstNode;
   currNode = currNode->next;

   while(currNode)
   {
      sortNode = lstNode;
      while (sortNode != grstNode )
      {
         if(currNode->probCount > sortNode->probCount)
         {
            sortNode = (Node*)sortNode->next;
         }
         else
         {
            tempCurrNode = (Node *)currNode->next;
            if (currNode->prev)
               currNode->prev->next =  currNode->next;
            if (currNode->next)
               currNode->next->prev = currNode->prev;
            if (sortNode->prev == NULL)
            {
               sortNode->prev = currNode;
               currNode->next = sortNode;
               currNode->prev = NULL;
               lstNode        = currNode;
               gNode          = lstNode;
            }
            else
            {
               currNode->next = sortNode;
               currNode->prev = sortNode->prev;
               sortNode->prev->next = currNode;
               sortNode->prev = currNode;

            }
#ifdef DEBUG
            printNodes();
#endif
            currNode = tempCurrNode;
            truth  = 1;
            break;
         }
      }
      /* Sometimes Functional optimizatin kills operational optimization */
      if (truth == 1) 
      {
         gNode = lstNode;
         currNode = tempCurrNode;
         truth = 0;
         continue;
      }
      if (sortNode == grstNode)
      {
         if (currNode->next == NULL)
         {
            grstNode = currNode;
         }
         else if(currNode->probCount < sortNode->probCount)
         {
            tempCurrNode = currNode->next;
            if (currNode->next)
               currNode->next->prev = sortNode;
            if (currNode->prev)
               currNode->prev->next = currNode->next;

            currNode->next = sortNode;
            currNode->prev = sortNode->prev;

            if (sortNode->prev)
            {
               sortNode->prev->next = currNode;
            }
            else
            {
               currNode->prev = NULL;
               lstNode = currNode;
            }
            sortNode->prev = currNode;
            currNode = tempCurrNode;
            grstNode = sortNode;
         }
         else
         {
            if (currNode->probCount > grstNode->probCount)
               grstNode = currNode;
            tempCurrNode = currNode->next;
         }
      }
      gNode = lstNode;
      currNode = tempCurrNode;
#ifdef DEBUG
      printNodes();
#endif
   }
   return;
}

void sortOnProbCount()
{
   int row, col, nr, nc;
   int i,j;

   gRunSuccess = 0;
   for (i=0; i<9; i++)
   {
      for (j=0; j<9; j++)
      {
         if (mBox[i/3][j/3].succSeq[i%3][j%3])
         {
            gRunSuccess++;
         }
         else
         {
            insertNode(i,j);
         }
      }
   }
#ifdef DEBUG
   printNodes();
#endif
   sortNodes();
   return;
}

int eliminatingMachine (Node *stkNode)
{
   int ret;
   int idx;
   Box tmpBox[3][3];

   if (stkNode == NULL)
   {
      return (FAILED);
   }
#ifdef DEBUG
   printf("Entering nr %d nc %d row %d col %d\n", stkNode->nr, stkNode->nc, stkNode->row, stkNode->col);
#endif
   memcpy(tmpBox, mBox, sizeof(mBox));
   for (idx = 0; idx < stkNode->probCount; idx++)
   {
      if (mBox[stkNode->nr][stkNode->nc].succSeq[stkNode->row][stkNode->col])
      {
#ifdef DEBUG
         printf("Data insuff stk nr %d nc %d row %d col %d\n", stkNode->nr, stkNode->nc, stkNode->row, stkNode->col);
#endif
         ret = DATINSUFF;
      }
      else
      {
#ifdef DEBUG
         printf("Else case testing with %d \n", stkNode->probSeq[idx]);
#endif
         mBox[stkNode->nr][stkNode->nc].succSeq[stkNode->row][stkNode->col]
           =  stkNode->probSeq[idx];
         mBox[stkNode->nr][stkNode->nc].probCount[stkNode->row][stkNode->col]
           =  1;
         ret = validateForSuccess();
      }
      if (ret == FAILED)
      {
#ifdef DEBUG
         printf("Failed %s %d\n", __FILE__, __LINE__);
#endif
         memcpy(mBox, tmpBox, sizeof(mBox));
         continue;
      }
      else if (ret == SUCCESS)
      {
         return (ret);
      }
      else if (ret == DATINSUFF)
      {
         solveSudoku();
         ret = validateForSuccess();
         if (ret == FAILED)
         {
#ifdef DEBUG
            printf("Failed after solving\n");
#endif
            memcpy(mBox, tmpBox, sizeof(mBox));
            continue;
         }
         else if (ret == SUCCESS)
         {
            return (ret);
         }
         else if (ret == DATINSUFF)
         {
            memcpy(mBox, tmpBox, sizeof(mBox));
            mBox[stkNode->nr][stkNode->nc].succSeq[stkNode->row][stkNode->col]
               =  stkNode->probSeq[idx];
             mBox[stkNode->nr][stkNode->nc].probCount[stkNode->row][stkNode->col]
           =  1;
            ret = eliminatingMachine(stkNode->next);
            if (ret == SUCCESS)
            {
                return(ret);
            }
            else
            {
               mBox[stkNode->nr][stkNode->nc].succSeq[stkNode->row][stkNode->col] = 0;
               memcpy(mBox, tmpBox, sizeof(mBox));
            }
         }
      }
   }
   memcpy(mBox, tmpBox, sizeof(mBox));
   return (FAILED);
}

void solveProbabilitySudoku()
{
   int ret;
   sortOnProbCount();
   ret = eliminatingMachine(gNode);
   if (ret == FAILED)
   {
      printf("Can't Solve Check your problem\n");
      exit(0);
   }
}

int main()
{
   int ret;
   struct timeval start, finish;
   readfile();
   solveSudoku();
   gettimeofday(&start, NULL);
#ifdef DEBUG
   printSudoku();
#endif
   if (validateForSuccess())
   {
#ifdef DEBUG
      printf("OMG .. Evil/Hard Problem\n");
#endif
      
      solveProbabilitySudoku();
   }
   gettimeofday(&finish, NULL);
   printf("Time taken %d sec %ld microsec\n", finish.tv_sec - start.tv_sec,
                                            finish.tv_usec - start.tv_usec);
   printSudoku();
   return 1;
}
